#ifndef FORDBELMAN_H
#define FORDBELMAN_H
#include "graph.h"
template <class vertexData, class edgeData>
void FordBelman(graph<vertexData,edgeData> g, typename graph<vertexData,edgeData>::vertexIterator start){
    typedef graph < vertexData,edgeData > graphType;
    typedef map< vertexData,edgeData > mapType;
     typedef pair< vertexData,edgeData > pairType;
    mapType fordMap;
    fordMap.insert(make_pair( *start,0));
    int size = 0;
    for (typename graphType::vertexIterator v = g.vertexBegin(); v != g.vertexEnd(); ++v){
        fordMap.insert(pair<vertexData,edgeData>(*v,30000));
        size++;
    }
        for (int j = 0; j < size; ++j){
            for (typename graphType::edgeIterator edge = g.edgeBegin(); edge != g.edgeEnd(); ++edge){
                if (fordMap.find(edge.first())->second < 30000 && fordMap.find(edge.second())->second > fordMap.find(edge.first())->second + (*edge)){
                        typename map<vertexData,edgeData>::iterator i = fordMap.find(edge.second());
                        fordMap.erase(i);
                        fordMap.insert(pairType(edge.second(),fordMap.find(edge.first())->second + *edge));
                    }
            }
        }
        //std::ofstream out ("OUTPUT.TXT");
        for (typename mapType::iterator i = fordMap.begin(); i != fordMap.end(); ++i){
            cout << i->second<<" ";
        }
}
#endif // FORDBELMAN_H
